{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #1-bit and 2-bit Characters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isOneBitCharacter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #1 比特与 2 比特字符"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有两种特殊字符：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>第一种字符可以用一比特&nbsp;<code>0</code> 表示</li>\n",
    "\t<li>第二种字符可以用两比特（<code>10</code>&nbsp;或&nbsp;<code>11</code>）表示</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个以 <code>0</code> 结尾的二进制数组&nbsp;<code>bits</code>&nbsp;，如果最后一个字符必须是一个一比特字符，则返回 <code>true</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> bits = [1, 0, 0]\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 唯一的解码方式是将其解析为一个两比特字符和一个一比特字符。\n",
    "所以最后一个字符是一比特字符。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>bits = [1,1,1,0]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>唯一的解码方式是将其解析为两比特字符和两比特字符。\n",
    "所以最后一个字符不是一比特字符。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= bits.length &lt;= 1000</code></li>\n",
    "\t<li><code>bits[i]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [1-bit-and-2-bit-characters](https://leetcode.cn/problems/1-bit-and-2-bit-characters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [1-bit-and-2-bit-characters](https://leetcode.cn/problems/1-bit-and-2-bit-characters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,0]', '[1,1,1,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: list[int]) -> bool:\n",
    "        pre = False\n",
    "        ans = True\n",
    "        for i, b in enumerate(bits):\n",
    "            if i == len(bits) - 1:\n",
    "                ans = not pre\n",
    "            if b == 0 or (b == 1 and pre):\n",
    "                pre = False\n",
    "            else:\n",
    "                pre = True\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if bits[-1] == 1: return False\n",
    "        n = len(bits)\n",
    "        if n == 1:\n",
    "            return bits[0] == 0\n",
    "        if bits[-2] == 0: return True\n",
    "        bits = bits[:-2]\n",
    "        n -= 2\n",
    "        self.find = False\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                self.find = True\n",
    "                return\n",
    "            if bits[i] == 0:\n",
    "                dfs(i+1)\n",
    "            else:\n",
    "                if i<n-1:\n",
    "                    dfs(i+2)\n",
    "        dfs(0)\n",
    "        if self.find: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n = len(bits)\n",
    "        def f(i):\n",
    "            if i==n-1:\n",
    "                return True\n",
    "            elif i==n-2:\n",
    "                return bits[i]!=1\n",
    "            else:\n",
    "                if bits[i]==0:\n",
    "                    return f(i+1)\n",
    "                else:\n",
    "                    return f(i+2)\n",
    "        return f(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if len(bits) == 1:\n",
    "            return True\n",
    "\n",
    "        dp = [-1] * len(bits)\n",
    "        def valid(end):\n",
    "            if end < 0:\n",
    "                return True\n",
    "            if dp[end] != -1:\n",
    "                return dp[end]\n",
    "            if bits[end] == 0:\n",
    "                if valid(end-1):\n",
    "                    return True\n",
    "            if end > 0 and bits[end-1] == 1:\n",
    "                return valid(end-2)\n",
    "            return False\n",
    "\n",
    "        if valid(len(bits)-3) and bits[-2] == 1:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        i,n = 0,len(bits)\n",
    "        while i < n - 1 :\n",
    "            i += bits[i] + 1\n",
    "        return i == n - 1    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n = len(bits)\n",
    "        one = False\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if bits[i] == 1:\n",
    "                one = False\n",
    "                i += 2\n",
    "            else:\n",
    "                one = True\n",
    "                i += 1\n",
    "        \n",
    "        return one"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n = len(bits)\n",
    "        i = 0\n",
    "        while i < n - 1: \n",
    "            if bits[i] == 1:\n",
    "                i += 2\n",
    "            else:\n",
    "                i += 1\n",
    "        return i == n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        i, l = 0, len(bits)\n",
    "        while i < l:\n",
    "            if bits[i] == 1:\n",
    "                i += 2\n",
    "            elif bits[i] == 0 and i == l - 1:\n",
    "                return True\n",
    "            else:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\r\n",
    "        L = len(bits)\r\n",
    "        idx = L - 2\r\n",
    "        while idx >= 0 and bits[idx]:\r\n",
    "            idx -= 1\r\n",
    "        return (L - idx) % 2 == 0\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "\n",
    "        def dfs(index):\n",
    "        \n",
    "            if index >= len(bits):\n",
    "                return False\n",
    "            if index == len(bits) - 1 and bits[index]==0:\n",
    "                return True\n",
    "            if index == len(bits) - 2 and bits[index]==1:\n",
    "                return False\n",
    "            if bits[index]==0:\n",
    "                return dfs(index+1)\n",
    "            else:\n",
    "                return dfs(index+2)\n",
    "\n",
    "        return dfs(0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        def dfs(i):\n",
    "            if i == n-1:\n",
    "                return True\n",
    "            for j in [i,i+1]:\n",
    "                if bits[i:j+1] in ([0],[1,0],[1,1]):\n",
    "                    if dfs(j+1):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        n = len(bits)\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        idx = 0\n",
    "        while len(bits) > 1:\n",
    "            if bits[0] == 1:\n",
    "                bits.pop(0)\n",
    "                bits.pop(0)\n",
    "            elif bits[0] == 0:\n",
    "                bits.pop(0)\n",
    "        if bits == []:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        length = len(bits)\n",
    "        i = length - 2\n",
    "        while i>=0 and bits[i]:\n",
    "            i-=1\n",
    "        return (length-i)%2==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        i, n = 0, len(bits) - 1\n",
    "        while i < n:\n",
    "            i += bits[i] + 1\n",
    "        return i == n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n = len(bits)\n",
    "        pos = 0\n",
    "        while pos < n - 1:\n",
    "            pos += 2 if bits[pos] == 1 else 1\n",
    "        return pos == n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "      \n",
    "        n = len(bits)\n",
    "        idx = 0\n",
    "        while idx < n-1:\n",
    "            if bits[idx] == 0:\n",
    "                idx += 1\n",
    "            else:\n",
    "                idx +=2\n",
    "        return idx == n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        # 正序遍历(有点模糊)\n",
    "        # 第一种字符一定以 0 开头，第二种字符一定以 1 开头\n",
    "        i, n = 0, len(bits)\n",
    "        while i < n-1:\n",
    "            i += bits[i] + 1 # 遇到第一种字符0，跳到下一个位置；遇到第二种字符1，跳到后第二个位置\n",
    "        return i == n-1\n",
    "\n",
    "        # 倒序遍历（没看懂）\n",
    "        # 0一定是一个字符的结尾\n",
    "        # 已知最后一位必是0，倒数第二个0位置记为i，i+1一定是字符的开头\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        # 22:04 -> 22:09\n",
    "        def is_valid(i):\n",
    "            if i == len(bits):\n",
    "                return True\n",
    "            if bits[i] == 0:\n",
    "                return is_valid(i + 1)\n",
    "            elif i == len(bits) - 1:\n",
    "                return False\n",
    "            else:\n",
    "                return is_valid(i + 2)\n",
    "\n",
    "        bits = bits[:-1]\n",
    "        return is_valid(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if len(bits)==1:\n",
    "            return True\n",
    "        \n",
    "        i=len(bits)-2\n",
    "        count=0\n",
    "        while i>=0:\n",
    "            if bits[i]==1:\n",
    "                count+=1\n",
    "            else:\n",
    "                break\n",
    "            i-=1\n",
    "        if count%2==0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n = len(bits)\n",
    "        pos = 0\n",
    "        while pos < n - 1:\n",
    "            if bits[pos] == 1:\n",
    "                pos += 2\n",
    "            else:\n",
    "                pos += 1\n",
    "        if pos == n - 1: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n = len(bits)\n",
    "        i = n - 2\n",
    "        while i >= 0 and bits[i]:\n",
    "            i -= 1\n",
    "        return (n - i) % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if len(bits) == 1 or bits[-2] == 0:  # 最后两位为 \"00\" 的情况\n",
    "            return True\n",
    "        else:  # 最后两位为 \"10\" 的情况\n",
    "            new_bits = bits[:-2]\n",
    "            length = len(new_bits)\n",
    "            i = 0\n",
    "            while i < length:\n",
    "                if new_bits[i] == 1:\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            return False if i == length else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        count = 0\n",
    "        i = len(bits) - 2\n",
    "        while i > -1 and bits[i]:\n",
    "            count += 1\n",
    "            i -= 1\n",
    "        return count % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        i, n = 0, len(bits)\n",
    "        while i < n - 1:\n",
    "            i += bits[i] + 1\n",
    "        return i == n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        i, n = 0, len(bits)\n",
    "        while i < n - 1:\n",
    "            i += bits[i] + 1\n",
    "        return i == n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        i = 0\n",
    "        n = len(bits)\n",
    "        while i < n - 1:\n",
    "            if bits[i] == 0:\n",
    "                i += 1\n",
    "            elif bits[i] == 1:\n",
    "                if i == n - 2:\n",
    "                    return False\n",
    "                i += 2\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if len(bits) == 1 or bits[-2] == 0:\n",
    "            return True\n",
    "        # \n",
    "        i = 0\n",
    "        # flag = False\n",
    "        while i < len(bits) - 2:\n",
    "            if bits[i] == 1:\n",
    "                i += 2\n",
    "                # flag = False\n",
    "            else:\n",
    "                i += 1\n",
    "                # flag = True\n",
    "        return bits[i:] == [0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n = len(bits)\n",
    "        if n == 1:\n",
    "            return True\n",
    "        i = 0\n",
    "        while i <= n - 2:\n",
    "            if bits[i] == 0:\n",
    "                i += 1\n",
    "            else:\n",
    "                i += 2\n",
    "            \n",
    "            if i == n-1:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if len(bits)==1:\n",
    "            return True\n",
    "        \n",
    "        i=len(bits)-2\n",
    "        count=0\n",
    "        while i>=0:\n",
    "            if bits[i]==1:\n",
    "                count+=1\n",
    "                i-=1\n",
    "            else:\n",
    "                break\n",
    "        if count%2==0:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        i=0\n",
    "        while i<len(bits)-1:\n",
    "            if bits[i]==1:\n",
    "                i=i+2\n",
    "            else:\n",
    "                i=i+1\n",
    "        return i==len(bits)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        i, res = 0, True\n",
    "        while i < len(bits):\n",
    "            if bits[i] == 1:\n",
    "                i += 2\n",
    "                res = False\n",
    "            else:\n",
    "                i += 1\n",
    "                res = True\n",
    "        return res if i == len(bits) else False\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "      idx = 0\n",
    "      while idx < len(bits):\n",
    "        if idx == len(bits) - 1 and bits[idx] == 0:\n",
    "          return True\n",
    "        if bits[idx] == 0:\n",
    "          idx += 1\n",
    "        else:\n",
    "          idx += 2\n",
    "      return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n = len(bits)\n",
    "        i = 0\n",
    "        while i < n-1:\n",
    "            if bits[i]==1:\n",
    "                i += 2\n",
    "            else:\n",
    "                i += 1\n",
    "        return i==n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        #仅一位且是0\n",
    "        if len(bits) == 1 and bits[-1] == 0:\n",
    "            return True\n",
    "\n",
    "        #多位把最后一位去掉，能走到底就说明成立\n",
    "        currlength = 0\n",
    "        while currlength < len(bits)-1:\n",
    "            if bits[currlength] == 0:\n",
    "                currlength += 1\n",
    "            else:\n",
    "                currlength += 2\n",
    "\n",
    "        return currlength == len(bits)-1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        last=-1\n",
    "        lenth=len(bits)\n",
    "        if bits[lenth-1]!=0:\n",
    "            return False\n",
    "        for i in range(lenth-1):\n",
    "            if bits[i]==0:\n",
    "                last=-1\n",
    "            elif bits[i]==1 and last==1:\n",
    "                last=-1\n",
    "            elif bits[i]==1 and last==-1:\n",
    "                last=1\n",
    "        return last==-1 \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n = len(bits)\n",
    "        if bits[n-2] == 0:\n",
    "            return True\n",
    "        else:\n",
    "            i = n-2\n",
    "            while bits[i]:\n",
    "                i-=1\n",
    "            return False if (n-2-i)%2 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if len(bits)==1:\n",
    "            return True\n",
    "        if bits[-2]==0:\n",
    "            return True\n",
    "        cur=0\n",
    "        while cur<len(bits)-2:\n",
    "            if bits[cur]==0:\n",
    "                cur+=1\n",
    "            else:\n",
    "                cur+=2\n",
    "        return cur==len(bits)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if len(bits) == 1 or bits[-2] == 0:\n",
    "            return True\n",
    "        # \n",
    "        i = 0\n",
    "        flag = False\n",
    "        while i < len(bits):\n",
    "            if bits[i] == 1:\n",
    "                i += 2\n",
    "                flag = False\n",
    "            else:\n",
    "                i += 1\n",
    "                flag = True\n",
    "        return flag\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n=len(bits)\n",
    "        i=0\n",
    "        while i <n-1:\n",
    "            # 10 11 ，1 开头二笔特\n",
    "            if bits[i]==1:\n",
    "                i+=2\n",
    "            else:\n",
    "                i+=1\n",
    "        print(i)\n",
    "        print(n)\n",
    "        return i==n-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        i, n = 0, len(bits)\n",
    "        while i < n - 1:\n",
    "            i += bits[i] + 1\n",
    "        return i == n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if bits is None or len(bits) == 0 or bits[-1] == 1:\n",
    "            return False\n",
    "        \n",
    "        if len(bits) == 1 or bits[-2] == 0:\n",
    "            return True\n",
    "        \n",
    "        i = len(bits) - 3\n",
    "        while i >= 0 and bits[i] == 1:\n",
    "            i -= 1\n",
    "        \n",
    "        return (len(bits) - 2 - i) & 1 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        pos=0\n",
    "        while pos<len(bits)-1:\n",
    "            pos+=2 if bits[pos]==1 else 1\n",
    "        return pos==len(bits)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n  = len(bits)\n",
    "        i = 0\n",
    "        while i < n-1:\n",
    "            cur = bits[i]\n",
    "            if cur == 1:\n",
    "                i += 1\n",
    "            i += 1\n",
    "        return i == n-1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits):\n",
    "        i = 0\n",
    "        while i < len(bits) - 1:\n",
    "            if bits[i] == 0:\n",
    "                i += 1\n",
    "            else:\n",
    "                i += 2\n",
    "        return i == len(bits) - 1 and bits[i] == 0\n",
    "\n",
    "# 测试用例\n",
    "test_case_1 = [1, 0, 0]\n",
    "print(Solution().isOneBitCharacter(test_case_1))  # 期望输出: True\n",
    "\n",
    "test_case_2 = [1, 1, 1, 0]\n",
    "print(Solution().isOneBitCharacter(test_case_2))  # 期望输出: False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "\n",
    "        i, n = 0, len(bits)\n",
    "        while i < n - 1:\n",
    "            i += bits[i] + 1\n",
    "        return i == n - 1\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/1-bit-and-2-bit-characters/solutions/1264760/1bi-te-yu-2bi-te-zi-fu-by-leetcode-solut-rhrh/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if len(bits)==1:\n",
    "            return True\n",
    "        if bits[-2]==0:\n",
    "            return True\n",
    "        cur=0\n",
    "        while cur<len(bits)-2:\n",
    "            if bits[cur]==0:\n",
    "                cur+=1\n",
    "            else:\n",
    "                cur+=2\n",
    "        return cur==len(bits)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        # return bool((len(bits)%2 and (not(bits[-2]==1 and bits[-3]==0) if len(bits)>2 else True) ) or (not len(bits)%2 and(1 not in bits) or (bits[-2]==0)or not(bits[-2]==1 and bits[-3]==0)))\n",
    "        i, n = 0, len(bits)\n",
    "        while i < n - 1:\n",
    "            i += bits[i] + 1\n",
    "        return i == n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if bits == [0] or bits[-2:] == [0, 0]: # bits可能为[0]\n",
    "            return True\n",
    "        else: # 列表以[1, 0]结尾时，需要判断列表中最后出现的连续的1的个数\n",
    "            i, count = len(bits)-2, 0\n",
    "            while bits[i] and i >= 0:\n",
    "                count += 1\n",
    "                i -= 1\n",
    "            else:\n",
    "                return False if count % 2 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        for i in range(len(bits)-1):\n",
    "            if(bits[i]==0):\n",
    "                bits[i]=-1\n",
    "                \n",
    "            if(bits[i]==1):\n",
    "                bits[i]=-1\n",
    "                bits[i+1]=-1\n",
    "                \n",
    "        if 0 in bits:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if 1 not in set(bits):return True\n",
    "        i=0\n",
    "        n=len(bits)\n",
    "        ok=False\n",
    "        while i<n:\n",
    "            if ok:\n",
    "                ok=False\n",
    "            elif bits[i]==1:ok=True\n",
    "            i+=1\n",
    "            if i==n-1:return not ok\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        i=0\n",
    "        while(i<len(bits)-1):\n",
    "            if bits[i]==1:\n",
    "                i+=2\n",
    "            else: i+=1\n",
    "        return i!=len(bits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        length=len(bits)\n",
    "        i=0\n",
    "        while i<length:\n",
    "            if bits[i]==0:\n",
    "                i+=1\n",
    "            else:\n",
    "                i+=2\n",
    "                if i==length:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        for i in range(len(bits)):\n",
    "            if i == len(bits)-2 and bits[i] == 1:\n",
    "                return False\n",
    "            if bits[i] == 1:\n",
    "                bits.remove(1)\n",
    "            if bits[i] == 0 and i == len(bits) -1:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        bits = [str(i) for i in bits]\n",
    "        ss = ''.join(bits)\n",
    "        ss = ss.replace('11','s').replace('10','s')    \n",
    "        \n",
    "        if ss[-1] != '0':\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\r\n",
    "        has_one=False\r\n",
    "        for bit in bits[:-1]:\r\n",
    "            if has_one:\r\n",
    "                has_one=False\r\n",
    "                continue\r\n",
    "            if bit==1:\r\n",
    "                has_one=True\r\n",
    "        return not has_one"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        l = len(bits) \n",
    "        i = 0\n",
    "        while i < l - 1:\n",
    "            print(i)\n",
    "            tmp = 10 * bits[i] + bits[i + 1]\n",
    "            if tmp == 11 or tmp == 10:\n",
    "                i += 2\n",
    "                continue\n",
    "            else:\n",
    "                i += 1\n",
    "        if i == l - 1:\n",
    "            return bits[i] == 0\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n = len(bits)\n",
    "        i = n - 2\n",
    "        while i >= 0 and bits[i]:\n",
    "            i -= 1\n",
    "        return (n - i) % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if len(bits)==1:\n",
    "            return True\n",
    "        if bits[-2]==0:\n",
    "            return True\n",
    "        cur=len(bits)-2\n",
    "        while cur>=0 and bits[cur]==1:\n",
    "            cur-=1\n",
    "        l=len(bits)-cur\n",
    "        return l%2==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        # i = 0\n",
    "        # while (i < len(bits)):\n",
    "        #     if bits[i] == 1:\n",
    "        #         i += 2\n",
    "        #         if i == len(bits):\n",
    "        #             return False\n",
    "        #     if bits[i] == 0:\n",
    "        #         i += 1\n",
    "        #         if i == len(bits):\n",
    "        #             return True\n",
    "        i, n = 0, len(bits)\n",
    "        while i < n - 1:\n",
    "            i += bits[i] + 1\n",
    "        return i == n - 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        i = 0\n",
    "        while i <= len(bits) - 2:\n",
    "            if bits[i] == 0:\n",
    "                i += 1\n",
    "            else:\n",
    "                i += 2\n",
    "        return i == len(bits) - 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if len(bits) == 1 or bits[-2] == 0:\n",
    "            return True\n",
    "        idx = 0\n",
    "        while idx < len(bits) - 2:\n",
    "            idx += bits[idx] + 1\n",
    "        return idx == len(bits) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        bits = ''.join(map(str,bits))\n",
    "        bits = bits.replace('11','*')\n",
    "        bits = bits.replace('10','*')\n",
    "        if bits[-1] != '*': return True\n",
    "        else: return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        while True:\n",
    "            if len(bits) == 1:\n",
    "                return True\n",
    "            if len(bits) == 2:\n",
    "                return bits[0] == 0\n",
    "            if bits[0] ==0:\n",
    "                bits.pop(0)\n",
    "            else:\n",
    "                bits.pop(0)\n",
    "                bits.pop(0)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        t = [False] * len(bits)\n",
    "        i = 0\n",
    "        while i < len(bits) :\n",
    "            if bits[i] == 1 :\n",
    "                t[i] = True\n",
    "                t[i + 1] = True\n",
    "                i += 2\n",
    "            else : i += 1\n",
    "\n",
    "        return t[-1] == False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n, cur = len(bits), 0\n",
    "        if n == 0: return False\n",
    "        while cur < n:\n",
    "            if cur == n - 1 and bits[cur] == 0:\n",
    "                return True\n",
    "            if bits[cur] == 1:\n",
    "                cur += 2\n",
    "            else:\n",
    "                cur += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        data = bits\n",
    "        n = len(data)\n",
    "        count = 0\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if data[i] == 1:\n",
    "                count += 1\n",
    "            else:\n",
    "                break\n",
    "        return True if count % 2 == 0 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "\n",
    "        i = 0\n",
    "        pre = -1\n",
    "        while i < len(bits):\n",
    "            if bits[i] == 0:\n",
    "                i += 1\n",
    "                pre = 1\n",
    "            else:\n",
    "                i += 2\n",
    "                pre = 2\n",
    "        return True if pre == 1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n = len(bits)\n",
    "\n",
    "        i = n - 2\n",
    "\n",
    "        while i >= 0 and bits[i]:\n",
    "\n",
    "            i -= 1\n",
    "        \n",
    "        return (n - i) % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        return False if not bits or bits == [[1, 0]] else True if bits == [0] else self.isOneBitCharacter(bits[1:]) if bits[0] == 0 else self.isOneBitCharacter(bits[2:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        lenb=len(bits)\n",
    "        z1=0\n",
    "        z2=1\n",
    "        bits=bits[::-1]\n",
    "        for i in range(lenb):\n",
    "            if bits[i]==0:\n",
    "                z1+=1\n",
    "                if z1==2:\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        for i in range(z1,lenb):\n",
    "            if bits[i]==1:\n",
    "                z2 ^=1\n",
    "            else:\n",
    "                break\n",
    "        return True if z1==2 else bool(z2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        i=0\n",
    "        while i < len(bits):\n",
    "            if bits[i] == 0:\n",
    "                if i == len(bits) - 1:\n",
    "                    return True\n",
    "                i+=1\n",
    "            else:\n",
    "                i+=2\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        length = len(bits)\n",
    "        if length <= 1: return True\n",
    "        if bits[-1]:    return False\n",
    "\n",
    "        @lru_cache\n",
    "        def helper(idx):\n",
    "            if idx < 0: return True\n",
    "            if bits[idx]:\n",
    "                if idx == 0 or bits[idx - 1] == 0:\n",
    "                    return False\n",
    "                return helper(idx - 2)\n",
    "            else:\n",
    "                return helper(idx - 1) or helper(idx - 2)\n",
    "\n",
    "        return helper(length - 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isOneBitCharacter(self, bits):\n",
    "        \"\"\"\n",
    "        :type bits: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        endNum = 0\n",
    "        i = 0\n",
    "        while i < len(bits):\n",
    "            print(i)\n",
    "            endNum = bits[i]\n",
    "            if(bits[i]==1):\n",
    "                i+=1\n",
    "            i += 1\n",
    "            print(endNum)\n",
    "        if(endNum==1):\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        if len(bits) >= 3:\n",
    "            if int(bits[len(bits) - 2]) == 0:\n",
    "                return True\n",
    "            else:\n",
    "                bits.reverse()\n",
    "                one = 0\n",
    "                for ones in range(2,len(bits)):\n",
    "                    print(ones, bits, one)\n",
    "                    if bits[ones] != 0:\n",
    "                        one += 1\n",
    "                    if ones == len(bits) - 1 or bits[ones] == 0:\n",
    "                        if one % 2 == 0:\n",
    "                            return False\n",
    "                        else:\n",
    "                            return True\n",
    "        else:\n",
    "            if bits == [1,0] or bits == [1,1]:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        i=0\n",
    "        nums=len(bits)\n",
    "        while 1:\n",
    "            if nums-1==i:return True\n",
    "            elif nums-2==i and bits[i]==0 : return True\n",
    "            elif i == nums - 2:    return False\n",
    "            elif bits[i]==1:\n",
    "                i=i+2\n",
    "            elif bits[i]==0:\n",
    "                i=i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        return False if not bits or bits == [[1, 0]] else True if bits == [0] else self.isOneBitCharacter(bits[1:]) if bits[0] == 0 else self.isOneBitCharacter(bits[2:])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        n=len(bits)\n",
    "        res=[]\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if bits[i]==0:\n",
    "                res.append('0')\n",
    "                i+=1\n",
    "            else:\n",
    "                if i+1<n:\n",
    "                    res.append(str(bits[i])+str(bits[i+1]))\n",
    "                    i+=2\n",
    "        print(res)\n",
    "        return res[-1]=='0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isOneBitCharacter(self, bits: List[int]) -> bool:\n",
    "        res = []\n",
    "        bits = list(map(str,bits))\n",
    "        bits = list(reversed(bits))\n",
    "        #print(bits)\n",
    "        while bits:\n",
    "            if len(bits) == 1 and bits[-1] == '1':\n",
    "                return False\n",
    "            if bits[-1] == '1':\n",
    "                res.append(bits[-1] + bits[-2])\n",
    "                bits.pop()\n",
    "                bits.pop()\n",
    "                continue\n",
    "            if bits[-1] == '0':\n",
    "                res.append(bits[-1])\n",
    "                bits.pop()\n",
    "                continue\n",
    "        #print(res)\n",
    "        if res[-1] == '0':\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
